package pl.enigmatic.math.perm;

import java.lang.reflect.Constructor;
import java.util.ArrayList;
import java.util.List;

import pl.enigmatic.util.Arrays;


public class PermutationFactory<P extends Permutation> {

	private final Class<P> clazz;
	private final Constructor<P> constructor;

	public PermutationFactory(final Class<P> cls) {
		this.clazz = cls;
		Constructor<P> c = null;
		try {
			c = clazz.getConstructor(int[].class);
		} catch (final Exception e) {}
		constructor = c;
	}

	public List<P> createAll(final int length) {
		final List<P> list = new ArrayList<P>();
		final int[] tab = Arrays.identity(length);
		boolean next = true;
		while (next) {
			try {
				list.add(constructor.newInstance(tab));
			} catch (final Exception e) {}
			int index = length - 1;
			while (index > 0 && tab[index] < tab[index - 1]) {
				index--;
			}
			if (next = index > 0) {
				final int[] tmp = new int[length - index + 1];
				int i = tmp.length - 1;
				int smallest = index;
				while (smallest < length - 1 && tab[smallest + 1] > tab[index - 1]) {
					tmp[i--] = tab[smallest];
					smallest++;
				}
				tmp[0] = tab[smallest];
				for (i = 0; i < length - smallest - 1; i++) {
					tmp[i + 1] = tab[length - i - 1];
				}
				tmp[++i] = tab[index - 1];
				for (i = 0; i < tmp.length; i++) {
					tab[tab.length - tmp.length + i] = tmp[i];
				}
			}
		}
		return list;
	}
}
